# 21/100 矩阵-旋转图像
# leetcode第240题: https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/1/1
from leetcode import test


def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    """比较首行元素，然后使用二分法进行检索，"""
    m, n = len(matrix), len(matrix[0])
    for i in range(m):
        if matrix[i][0] == target:
            return True
        if matrix[i][0] < target:
            l, r = 0, n - 1
            while l <= r:
                mid = ((r - l) >> 1) + l
                if matrix[i][mid] == target:
                    return True
                elif matrix[i][mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
    return False


def searchMatrix_opt(matrix: list[list[int]], target: int) -> bool:
    """从右上角开始搜索，如果元素的值小于target，则因为最右侧元素一定是该行最大值，所以可以判断可能的元素一定在该行以下，所以向下移动
    如果元素的值大于target，因为右侧的值一定大于左侧值，所以则向左移动来寻找target。
    """
    m, n = len(matrix), len(matrix[0])
    x, y = 0, n - 1
    while x < m and y >= 0:
        if matrix[x][y] == target:
            return True
        if matrix[x][y] > target:
            y -= 1  # 向左查找
        else:
            x += 1  # 向下查找
    return False


if __name__ == '__main__':
    inp = [{"matrix": [[1, 4, 7, 11, 15],
                       [2, 5, 8, 12, 19],
                       [3, 6, 9, 16, 22],
                       [10, 13, 14, 17, 24],
                       [18, 21, 23, 26, 30]],
            "target": 5},

           {"matrix": [[1, 4, 7, 11, 15],
                       [2, 5, 8, 12, 19],
                       [3, 6, 9, 16, 22],
                       [10, 13, 14, 17, 24],
                       [18, 21, 23, 26, 30]],
            "target": 23},

           {"matrix": [[1, 4, 7, 11, 15],
                       [2, 5, 8, 12, 19],
                       [3, 6, 9, 16, 22],
                       [10, 13, 14, 17, 24],
                       [18, 21, 23, 26, 30]],
            "target": 20}, ]

    out = [True, True, False]

    test.test_function(searchMatrix, inp, out, times=1000)
    test.test_function(searchMatrix_opt, inp, out, times=1000)
